Bidding to the Top: VCG and Equilibria of Position-Based Auctions

摘要

Many popular search engines run an auction to determine the placement ofadvertisements next to search results. Current auctions at Google and Yahoo!let advertisers specify a single amount as their bid in the auction. This bidis interpreted as the maximum amount the advertiser is willing to pay per clickon its ad. When search queries arrive, the bids are used to rank the adslinearly on the search result page. The advertisers pay for each user whoclicks on their ad, and the amount charged depends on the bids of all theadvertisers participating in the auction. In order to be effective, advertisersseek to be as high on the list as their budget permits, subject to the market. We study the problem of ranking ads and associated pricing mechanisms whenthe advertisers not only specify a bid, but additionally express theirpreference for positions in the list of ads. In particular, we study "prefixposition auctions" where advertiser $i$ can specify that she is interested onlyin the top $b_i$ positions. We present a simple allocation and pricing mechanism that generalizes thedesirable properties of current auctions that do not have position constraints.In addition, we show that our auction has an "envy-free" or "symmetric" Nashequilibrium with the same outcome in allocation and pricing as the well-knowntruthful Vickrey-Clarke-Groves (VCG) auction. Furthermore, we show that thisequilibrium is the best such equilibrium for the advertisers in terms of theprofit made by each advertiser. We also discuss other position-based auctions.